package 力扣日常刷题.木22二月.第14天220;

import 力扣日常刷题.TreeNode;

/**
 * @author 帅小伙
 * @date 2022/2/20
 * @description
 */
public class Demo110二叉树最大路径和 {

    int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if(node == null) return 0;
        int lG = maxGain(node.left);
        int rG = maxGain(node.right);
        int t = lG + rG + node.val;
        maxSum = Math.max(t,maxSum);
        return node.val + Math.max(lG,rG);
    }

}
